144. Binary Tree Preorder Traversal

tags: Easy、Tree

Given the root of a binary tree, return the preorder traversal of its nodes' values.

解法: 遞迴

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void preordertrace(struct TreeNode* node, int* array, int* index) {
   if (!node) {
        return ;
    }
    array[(*index)++] = node->val;
    preordertrace(node->left, array, index);
    preordertrace(node->right, array, index); 
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }

    int* array = (int*)malloc(100 * sizeof(int));

    //藉由遞迴來處理前序，並將訪問到的node放入array中
    int index = 0;
    preordertrace(root, array, &index);
    *returnSize = index;
    return array;
}

222. Count Complete Tree Nodes

tags: Easy、Tree

Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.

解法: 遞迴

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int countNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

543. Diameter of Binary Tree

tags: Easy、Tree

Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int getheight(struct TreeNode* node, int* diameter) {
    if (!node) {
        return 0;
    }
    int left_h = getheight(node->left, diameter);
    int right_h = getheight(node->right, diameter);

    *diameter = MAX(*diameter, left_h + right_h);
    return MAX(left_h, right_h) + 1;
}

int diameterOfBinaryTree(struct TreeNode* root) {
    int diameter = 0;
    getheight(root, &diameter);
    return diameter;
}